import org.omg.PortableInterceptor.INACTIVE;

import java.util.*;

public class project {
    public int rob(int[] nums) {
        int len=nums.length;
        if(len==1){
            return nums[0];
        }else if(len==2){
            return Math.max(nums[0],nums[1]);
        }else{
            return Math.max(robs(nums,0,len-2),robs(nums,1,len-1));
        }
    }
    public int robs(int[] nums,int start,int end){
        int sum=nums[start];
        int res=Math.max(nums[start+1],sum);
        for(int i=start+2;i<=end;i++){
            int tmp=res;
            res=Math.max(res,sum+nums[i]);
            sum=tmp;
        }
        return res;
    }












    public int rob3(int[] nums) {
        int len=nums.length;
        if(len==1){
            return nums[0];
        }else if(len==2){
            return Math.max(nums[0],nums[1]);
        }else{
            return Math.max(robs1(nums,0,len-1),robs(nums,1,len));
        }
    }
    public int robs1(int[] nums,int left,int right){
        int sum=nums[left];
        int res=Math.max(sum,nums[left+1]);
        for(int i=left+2;i<right;i++){
            int tmp=sum;
            res=Math.max(res,sum+nums[i]);
            sum=tmp;
        }
        return res;
    }










    public int lengthOfLongestSubstring(String s) {
        if(s==null||s.length()==0){
            return 0;
        }
        Map<Character,Integer> map=new HashMap<>();
        int max=0;
        int left=0;
        for(int i=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                left=Math.max(left,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max=Math.max(max,i-left+1);
        }
        return max;
    }



















    public int rob2(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        int len=nums.length;
        if(len==1){
            return nums[0];
        }
        int[] dp=new int[len];
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<len;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[len-1];
    }











    public int rob1(int[] nums) {
        int len=nums.length;
        int[] dp=new int[len];
        if(len<1){
            return nums[0];
        }
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<len;i++){
            dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);
        }
        return dp[len-1];
    }











    public boolean checkInclusion(String s1, String s2) {
        int len1=s1.length();
        int len2=s2.length();
        if(len1>len2){
            return false;
        }
        int[] arr1=new int[26];
        int[] arr2=new int[26];
        for(int i=0;i<len1;i++){
            arr1[s1.charAt(i)-'a']++;
            arr2[s2.charAt(i)-'a']++;
        }
        if(Arrays.equals(arr1,arr2)){
            return true;
        }
        for(int i=len1;i<len2;i++){
            arr2[s2.charAt(i-len1)-'a']--;
            arr2[s2.charAt(i)-'a']++;
            if(Arrays.equals(arr1,arr2)) {
                return true;
            }
        }
        return false;
    }











    public boolean checkInclusion1(String s1, String s2) {
        int len1=s1.length();
        int len2=s2.length();
        if(len1>len2){
            return false;
        }
        int[] arr1=new int[26];
        int[] arr2=new int[26];
        for(int i=0;i<len1;i++){
            arr1[s1.charAt(i)-'a']++;
            arr2[s2.charAt(i)-'a']++;
        }
        if(Arrays.equals(arr1,arr2)){
            return true;
        }
        for(int i=len1;i<len2;i++){
            arr2[s2.charAt(i-len1)-'a']--;
            arr2[s2.charAt(i)-'a']++;
            if(Arrays.equals(arr1,arr2)){
                return  true;
            }
        }
        return false;
    }










    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new LinkedList<>();
        int lens = s.length();
        int lenp = p.length();
        if (lens < lenp) {
            return list;
        }
        int[] arrs = new int[26];
        int[] arrp = new int[26];
        for (int i = 0; i < lenp; i++) {
            arrs[s.charAt(i) - 'a']++;
            arrp[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(arrs, arrp)) {
            list.add(0);
        }
        for (int i = lenp; i < lens; i++) {
            arrs[s.charAt(i - lenp) - 'a']--;
            arrs[s.charAt(i) - 'a']++;
            if (Arrays.equals(arrs, arrp)) {
                list.add(i - lenp + 1);
            }
        }
        return list;
    }


    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> list = new LinkedList<>();
        int lens = s.length();
        int lenp = p.length();
        if (lens < lenp) {
            return list;
        }
        int[] arrs = new int[26];
        int[] arrp = new int[26];
        for (int i = 0; i < lenp; i++) {
            arrs[s.charAt(i) - 'a']++;
            arrp[p.charAt(i) - 'a']++;
        }
        if (Arrays.equals(arrs, arrp)) {
            list.add(0);
        }
        for (int i = lenp; i < lens; i++) {
            arrs[s.charAt(i - lenp) - 'a']--;
            arrs[s.charAt(i) - 'a']++;
            if (Arrays.equals(arrs, arrp)) {
                list.add(i - lenp + 1);
            }
        }
        return list;
    }


    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i : nums) {
            set.add(i);
        }
        int res = 0;
        for (int s : set) {
            if (set.contains(s) == false) {
                int sum = 1;
                int tmp = s;
                while (set.contains(tmp + 1)) {
                    tmp += 1;
                    sum += 1;
                }
                res = Math.max(sum, res);
            }
        }
        return res;
    }


    public int longestConsecutive1(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int n : nums) {
            set.add(n);
        }
        int res = 0;
        for (int s : set) {
            if (set.contains(s - 1) == false) {
                int sum = 1;
                int tmp = s;
                while (set.contains(tmp + 1)) {
                    tmp += 1;
                    sum += 1;
                }
                res = Math.max(res, sum);
            }
        }
        return res;
    }
}
